#include "BigInteger.h"
#include <bitset>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <math.h>
#include <intrin.h>

int MaxUint = std::numeric_limits<unsigned int>::max();

#define VC2010
#ifndef VC2010
template<typename T>
std::string ToBinary(const T& value)
#else
std::string ToBinary(const unsigned int & value)
#endif
{
	/*
	Workaround to VC10 compiler bug:
	http://connect.microsoft.com/VisualStudio/feedback/details/532897/problems-constructing-a-bitset-from-an-unsigned-long-in-the-vc-rc
	*/
#ifdef VC2010
	const std::bitset<std::numeric_limits<const unsigned int>::digits + 1> bs(static_cast<unsigned long long>(value));
	const std::string s(bs.to_string());
#else
	const std::bitset<std::numeric_limits<T>::digits + 1> bs(value);
    const std::string s(bs.to_string());

#endif
	return s;
}

/*WARNING: credo a causa del workaround qui sopra, viene stampato uno zero in piu' all'inizio di ogni blocco di 32 bit */
void BigInteger::PrintBinary() const
{
	int size = this->buffer.size() - 1;
	for ( short i = size ; i >=0 ; --i){

		std::cout << ToBinary(buffer[i]) << " " ;
	}
	std::cout <<std::endl;
}


void BigInteger::initBuffer(unsigned int val)
{
	for (std::vector<unsigned int >::iterator it = buffer.begin() ; it != buffer.end() ; ++it){
		*it = val;	
	}

}
void BigInteger::init(unsigned int sliceN)
{
	this->buffer =  std::vector<unsigned int>(sliceN);
	
	this->MostSignificantSlice = 0;

}
void BigInteger::complement()
{
	int size = this->buffer.size();
	for (int i = 0 ; i <  size; ++i)
	{
		this->buffer[i] = ~this->buffer[i];
	}
	this->operator+= (1);
}

void BigInteger::reserveMoreSpace(int moreSpace)
{
	this->buffer.reserve(this->buffer.size() + moreSpace);
	for (int i = 0 ; i < moreSpace; ++i){
		if (isPositive())
			this->buffer.push_back(0);
		else
			this->buffer.push_back(MaxUint);
	}
	
}
unsigned int BigInteger::MostSignificantBitIndex() const 
{
	unsigned long mostSignificantBitIndex = 0;
	
	if (isPositive()){
		_BitScanReverse(&mostSignificantBitIndex, this->buffer[MostSignificantSlice]);
	}else{
		_BitScanReverse(&mostSignificantBitIndex, (~this->buffer[MostSignificantSlice]) );
	}
	mostSignificantBitIndex += (MostSignificantSlice * 32);

	unsigned int _res = static_cast<unsigned int>  (mostSignificantBitIndex);

	return _res;
}

//dividend and divisor must be positive
BigInteger __EgyptianModule(const BigInteger& dividend, const BigInteger& divisor)
{
	if (dividend < divisor){
		BigInteger d = dividend;
		return d;
	}

	BigInteger one(1);
	BigInteger divisorPower = divisor;
	while(divisorPower <= dividend ){
		divisorPower <<=1;
	}
	divisorPower >>=1;

	BigInteger remainder = dividend - divisorPower;
	while(remainder >= divisor){
		divisorPower >>=1;
		if (remainder >= divisorPower){
			remainder -= divisorPower;
		}
	}
	return remainder;
}

//reference: http://mathforum.org/library/drmath/view/57574.html
//dividend and divisor must be positive
BigInteger __EgyptianDivision(const BigInteger& dividend, const BigInteger& divisor)
{
	if (dividend < divisor)
		return BigInteger(0);

	BigInteger one(1);
	BigInteger divisorPower = divisor;
	BigInteger quotient(0);
	unsigned int pow = 0;
	while(divisorPower <= dividend ){
		divisorPower <<=1;
		pow +=1;
	}
	divisorPower >>=1;
	pow -=1;
	BigInteger remainder = dividend - divisorPower; 
	BigInteger foo = one << pow;
	BigInteger bar = one << (pow + 1);
		
	quotient += (one << pow);

	while(remainder >= divisor){
		divisorPower >>=1;
		pow -=1;
		if (remainder >= divisorPower){
			remainder -= divisorPower;
			quotient += (one << pow);
		}
	}

	return quotient;
}
BigInteger EgyptianDivision(const BigInteger& dividend, const BigInteger& divisor)
{
	if (dividend.isPositive()){
		if (divisor.isPositive()){
			return __EgyptianDivision(dividend, divisor);
		}else{
			return -__EgyptianDivision(dividend, -divisor); 
		}
	}
	if (divisor.isPositive()){
		return -__EgyptianDivision(-dividend, divisor);
	}
	return __EgyptianDivision(-dividend, -divisor);
	
}
//reference: http://mathworld.wolfram.com/RussianMultiplication.html
BigInteger EthiopianMultiplication (const BigInteger& a, const BigInteger& b)
{
	BigInteger _a; 
	BigInteger _b; 
	BigInteger result(0);
	short int sign = 1;
	if (a.isPositive())
	{
		_a =a;
		
	}else{
		_a = -a;
		sign *= -1;
	}
	if (b.isPositive()){
		_b = b;
	}else{
		_b = -b;
		sign *= -1;
	}

	if (_a <= _b){
		while (_a >= 1){
			if (!_a.IsEven()){
				result += _b;
			}
			_b <<= 1;
			_a >>= 1;
		}	
	}else{
		while (_b >= 1){
	
			if (!_b.IsEven()){
				result += _a;
			}
			_b >>= 1;
			_a <<= 1;
		}	
	}


	if (sign > 0)
		return result;
	result.complement();
	return result;
}
/* ---------- CONSTRUCTORS -------------*/
BigInteger::BigInteger(){

	init(defaultSliceNum);
	initBuffer(0);
	
}

BigInteger::BigInteger(int val)
{
	init(defaultSliceNum);
	initBuffer(0);
		
	if (val < 0){
		int _val = -val;
		this->buffer[0] = _val;
		complement();
	}else{
		this->buffer[0] = val;
	}
}

BigInteger::BigInteger(unsigned int val){
	init(defaultSliceNum);
	initBuffer(0);
	
	this->buffer[0] = val;
}
BigInteger::BigInteger(const BigInteger& that)
{
	init(that.buffer.size());
	if (that.isPositive())
		initBuffer(0);
	else{
		initBuffer(MaxUint);
	}
	for (int i = 0 ; i <= that.MostSignificantSlice ; ++i){
		this->buffer[i] = that.buffer[i];
	}
	this->MostSignificantSlice = that.MostSignificantSlice;
	
}

BigInteger::BigInteger(const std::string& s)
{
	unsigned int maxDecimalForSlice = defaultSliceNum; 
	init(maxDecimalForSlice);

	int len = s.length() -1;
	BigInteger multiplicator(1);
	for(int i = len ; i >0; --i){
		int digit = atoi(s.substr(i,1).c_str());
		this->operator+=(multiplicator * digit);
		multiplicator *= 10;
	}
	std::string digit_char = s.substr(0,1);
	if (0 == digit_char.compare("-")){
		this->complement();
	}else{
		int digit = atoi(digit_char.c_str());
		this->operator+=(multiplicator * digit);
	}
}

/* ---------- DESTRUCTORS -------------*/

BigInteger::~BigInteger()
{
	
}

// ------------------ MEMBER OPERATORS ---------------------
BigInteger& BigInteger::operator =(const BigInteger& that)
{
	if (this != &that){
		this->buffer.clear();
		this->buffer.reserve(std::max(defaultSliceNum, that.MostSignificantSlice));
		
		int i;
		for ( i = 0 ; i <= that.MostSignificantSlice ; ++i ){
			this->buffer.push_back (that.buffer[i]);
		}
		unsigned sign = that.isPositive() ? 0x00 : MaxUint;
		int size = that.buffer.size();
		for ( ; i < size ; ++i ){
			this->buffer.push_back (sign);
		}
		this->MostSignificantSlice = that.MostSignificantSlice;
	}
	
	return *this;
}

bool BigInteger::operator ==(const BigInteger& that)
{
	if (this->isPositive() != that.isPositive() ||
		this->MostSignificantSlice != that.MostSignificantSlice)
		return false;
	int size = this->MostSignificantSlice;
	for ( short i=0 ; i <= size; ++i){
		if ((this->buffer[i] != that.buffer[i]))
		{
			return false;
		}
	}
	return true;
}

BigInteger& BigInteger::operator <<=(const int offset)
{
	if (offset == 0 )
		return *this;
	int size = this->buffer.size() ;

	if (offset / 32 > MostSignificantSlice){
		reserveMoreSpace((offset / 32 ) + defaultSliceNum);
	
	}
	if (size -1 == MostSignificantSlice){
		if (offset < sizeof(unsigned int) * defaultSliceNum){
			reserveMoreSpace(defaultSliceNum);
			
		}else{
			int toReserve = (sizeof(unsigned int) * 4) / offset;
			reserveMoreSpace(toReserve);
		}
		
	}
	
	size = this->buffer.size();
	for ( short i = size - 1 ; i >0 && (i  - (offset / 32) >= 0); --i){
		unsigned int * slice = &this->buffer[i];
		int delta = i - 1 - (offset / 32);
		
		unsigned int * sliceNextRight;
		unsigned int right = 0 ;
		if (delta >=0 ){
			sliceNextRight = &this->buffer[delta];
			right = offset % 32 == 0 ? 0:*sliceNextRight >> (32  - (offset %32));
		
		}
		unsigned int * sliceNextLeft = &this->buffer[i - (offset / 32)];
	
		unsigned int left = offset % 32 == 0 ? *sliceNextLeft :*sliceNextLeft << (offset % 32);
		unsigned int aux = left | right;
		if (i > MostSignificantSlice && aux != *slice){
			MostSignificantSlice = i;
		}
		*slice = aux ;
	}
	if (offset < 32)
		this->buffer[0] =  (this->buffer[0] << offset); 
	else 
		this->buffer[0] = 0; 
	return *this;
}
int getMostSignificantSlice(const BigInteger& num)
{
	unsigned int signMask = num.isPositive() ? 0 : MaxUint;
	int index = num.buffer.size() -1 ;

	while ( index >0  ){
		if (num.buffer[index] != signMask){
			break;
		}
		index -=1;
		
	}
	return index;
}
BigInteger& BigInteger::operator >>=(const int offset)
{
	if (offset == 0 )
		return *this;
	int size = this->buffer.size() - 1;
	bool positive = isPositive();
	unsigned long mostSignificantBitIndex;
	if (isPositive()){
		_BitScanReverse(&mostSignificantBitIndex, this->buffer[MostSignificantSlice]);
	}else{
		_BitScanReverse(&mostSignificantBitIndex, ~this->buffer[MostSignificantSlice]);
	}

	for ( short i = 0 ; i < size && (i  + (offset / 33) <= size); ++i){
	
		unsigned int * slice = &this->buffer[i];
		int delta = i + 1 + (offset / 33);
		unsigned int * sliceNextLeft;
		unsigned int left = 0 ;
		if (delta <= size ){
			sliceNextLeft = &this->buffer[i + 1 + (offset / 33)];
			left = *sliceNextLeft << (32  - (offset %32));
		
		}
		unsigned int * sliceNextRight = &this->buffer[i + (offset / 33)];
		unsigned int right = offset % 32 == 0 ? 0 :*sliceNextRight >> (offset % 32);
		unsigned int aux = left | right;
		
		*slice = aux ;
	}
	if (offset < 32){
		if (positive)
			this->buffer[size] =  (this->buffer[size] >> offset); 
		else
			this->buffer[size] =  (MaxUint << (32 - offset))|(this->buffer[size] >> offset); 
	}
	else {
		if (positive)
			this->buffer[size] = 0; 
		else
			this->buffer[size] = MaxUint; 
	}
	int diff = offset - mostSignificantBitIndex;
	
	this->MostSignificantSlice = getMostSignificantSlice(*this);
	return *this;
}

BigInteger& BigInteger::operator +=(const BigInteger& that)
{
	bool overflow = false;

	if (that.MostSignificantSlice >= this->buffer.size() -1 || this->MostSignificantSlice >= this->buffer.size() - 2){
		reserveMoreSpace((this->MostSignificantSlice ) +  defaultSliceNum);
	}
	unsigned int sign = that.isPositive() ? 0 : MaxUint;
	MostSignificantSlice = std::max(MostSignificantSlice, that.MostSignificantSlice);
	int size = this->buffer.size() ;
	for ( short i = 0 ; i < size ; ++i){
		unsigned a = this->buffer[i];
		unsigned b = (i <= that.buffer.size() - 1 ) ? that.buffer[i]: sign;
		if (!overflow){
			this->buffer[i] += b;
			
		}else{
			this->buffer[i] += 1;
			this->buffer[i] += b;
		}
		unsigned buf = this->buffer[i];
		if (this->buffer[i] < a || this->buffer[i] < b){
			overflow = true;
		}else{
			overflow = false;
		}
	
	}
	
	this->MostSignificantSlice = getMostSignificantSlice(*this);
	return *this;
}

BigInteger& BigInteger::operator %= (const BigInteger& that)
{
	*this = *this % that;
	return *this;
}
BigInteger& BigInteger::operator /= (const BigInteger& that)
{
	*this = EgyptianDivision(*this, that);
	return *this;
}
BigInteger& BigInteger::operator *= (const BigInteger& that)
{
	int sign = 1;

	
	if (this->buffer.size() < (this->buffer.size() + that.MostSignificantSlice)){
		int toReserve = that.MostSignificantSlice;
		reserveMoreSpace(toReserve);
	}

	if (!this->isPositive()){
		sign *= -1;
		this->complement();
	}
	BigInteger tmp = *this;
	BigInteger res = BigInteger(0);
	if (that.isPositive()){
		int size = that.MostSignificantSlice ;
		for (int i = 0; i <= size ; ++i){
			for (int j = 0 ; j < sizeof(unsigned int ) * 8; ++j){
				
				if ((that.buffer[i] & (0x01 << j)) != 0){
					res += tmp;
				}

				tmp <<= 1 ;
			}
		}

		*this = res;
	}else{
		sign *= -1;
		BigInteger that_aux = that;
		that_aux.complement();
		int size = that.MostSignificantSlice;
	
		for (int i = 0 ; i <= size ; ++i){
			for (int j = 0 ; j < sizeof(unsigned int ) * 8; ++j){
				if ((that_aux.buffer[i] & (0x01 << j)) != 0 ){
					res += tmp ; 	
				}
				tmp <<= 1 ; 

			}
		}
		*this = res;
	}
	if (sign == -1 )
		this->complement();

	return *this;
}
BigInteger& BigInteger::operator -= (const BigInteger& that)
{
	BigInteger _that = that;
	_that.complement();
	this->operator+= (_that);

	return *this;
}
BigInteger& BigInteger::operator ++(){
	return this->operator+= (1);
}
BigInteger BigInteger::operator ++(int )
{
	BigInteger tmp = *this;
	this->operator++(1);
	return tmp;
}
BigInteger& BigInteger::operator --(){
	return this->operator-= (1);
}
BigInteger BigInteger::operator --(int )
{
	BigInteger tmp = *this;
	this->operator--(1);
	return tmp;
}

BigInteger BigInteger::operator ~()
{
	BigInteger tmp = *this;
	for (short i = 0; i < tmp.buffer.size(); ++i){
		tmp.buffer[i] = ~tmp.buffer[i];   
	}

	return tmp;
}
/*----- NON MEMBER OPERATORS --------------*/

BigInteger operator +(const BigInteger& first,const BigInteger& second )
{
	BigInteger tmp = first;
	tmp += second;
	return tmp;
}
BigInteger operator -(const BigInteger& first,const BigInteger& second )
{
	BigInteger tmp = second;
	tmp.complement();
	tmp += first;
	return tmp;
}
BigInteger operator *(const BigInteger& first,const BigInteger& second )
{
	BigInteger tmp = first;
	tmp *= second;
	return tmp;
}
BigInteger operator %(const BigInteger& a, const BigInteger& b)
{
	if (a.isPositive()){
		if (b.isPositive()){
			return __EgyptianModule(a,b);
		}
		return __EgyptianModule(a,-b);
	}
	if (b.isPositive()){
		return - __EgyptianModule(-a,b);
	}
	return - __EgyptianModule(-a,-b);
}
BigInteger operator /(const BigInteger& first,const BigInteger& second )
{

	return EgyptianDivision(first, second);

}
//----------------COMPARISON MEMBER OPERATORS -------------------------------
bool operator <(const BigInteger & a, const BigInteger& b) 
{
	
	if (a.isPositive() && !b.isPositive())
		return false;
	if(!a.isPositive() && b.isPositive())
		return true;
	//both operands have same sign
	if (a.isPositive()){
		if (a.MostSignificantSlice != b.MostSignificantSlice){
			return a.MostSignificantSlice > b.MostSignificantSlice ? false : true;
		}
		
		for (int i = a.MostSignificantSlice ; i >= 0 ; --i){
			unsigned f = a.buffer[i];
			unsigned g = b.buffer[i];

			if (a.buffer[i] == b.buffer[i] )
				continue;
			if (a.buffer[i] >= b.buffer[i])
				return false;
			else
				return true;
		}
		return false;
	}else{
		if (a.MostSignificantSlice != b.MostSignificantSlice){
			return a.MostSignificantSlice > b.MostSignificantSlice ? true : false;
		}

		for (int i = a.MostSignificantSlice ; i >=0 ; --i){
			
			if (a.buffer[i] == MaxUint && b.buffer[i] == MaxUint)
				continue;
			if (a.buffer[i] >= b.buffer[i])
				return true;
			else 
				return false;
		}
		return false;
	}
}
bool operator <=(const BigInteger & a, const BigInteger& b)
{
	if (a.isPositive() && !b.isPositive())
		return false;
	if(!a.isPositive() && b.isPositive()  )
		return true;
	//both operands have same sign
	if (a.isPositive()){
		if (a.MostSignificantSlice != b.MostSignificantSlice){
			return a.MostSignificantSlice > b.MostSignificantSlice ? false : true;
		}
		for (int i = a.MostSignificantSlice ; i >= 0; --i){
			if (a.buffer[i] == 0 && b.buffer[i] == 0)
				continue;
			if (a.buffer[i] > b.buffer[i])
				return false;
			else
				return true;
		}
		return true;
	}else{
		if (a.MostSignificantSlice != b.MostSignificantSlice){
				return a.MostSignificantSlice > b.MostSignificantSlice ? true : false;
		}
		for (int i = a.MostSignificantSlice ; i >= 0; --i){
			
			if (a.buffer[i] == MaxUint && b.buffer[i] == MaxUint)
				continue;

			if (a.buffer[i] > b.buffer[i])
				return false;
			else
				return true;
		}
		return false;
	}
}
bool operator >=(const BigInteger & a, const BigInteger& b)
{
	return ! (a< b);
}
bool operator >(const BigInteger & a, const BigInteger& b)
{
	return ! (a<= b);
}
bool operator ==(const BigInteger & a,const BigInteger& b)
{
	if (a.MostSignificantSlice != b.MostSignificantSlice){
		return false;
	}

	int ret = memcmp(&a.buffer[0], &b.buffer[0], sizeof(unsigned int) * a.MostSignificantSlice);
	return ret == 0 ? true : false;
}
bool operator !=(const BigInteger & a,const BigInteger& b)
{
	return !(a == b);
}
BigInteger operator -(const BigInteger& a)
{
	BigInteger tmp = a;
	tmp.complement();
	return tmp;
}

// ------------------ BITWISE ----------------------------
BigInteger operator ~(const BigInteger& a)
{
	BigInteger tmp = a;
	int size = tmp.buffer.size();
	for (int i = 0 ; i < size ; i++){
		tmp.buffer[i] = ~ tmp.buffer[i];
	}
	return tmp;
}
BigInteger operator &(const BigInteger& a, const BigInteger& b)
{
	BigInteger tmp; 
	
	int diff =a.MostSignificantSlice - b.MostSignificantSlice; 
	if (diff >= 0){
		tmp = a;
		int size = b.buffer.size();
		for (int i = 0 ; i < size ; ++i){
			tmp.buffer[i] &= b.buffer[i];
		}
		for (int i = size; i < tmp.buffer.size() ; ++i){
			if (b.isPositive())
				tmp.buffer[i] &= 0x00;
			else
				tmp.buffer[i] &= MaxUint;
		}
		
	}else{
		tmp = b;
		int size = b.buffer.size();
		for (int i = 0 ; i < size ; ++i){
			tmp.buffer[i] &= a.buffer[i];
		}
		for (int i = size; i < tmp.buffer.size() ; ++i){
			if (a.isPositive())
				tmp.buffer[i] &= 0x00;
			else
				tmp.buffer[i] &= MaxUint;
		}
		
	}
	return tmp;
}
BigInteger operator |(const BigInteger& a, const BigInteger& b)
{
	BigInteger tmp; 
	
	int diff =a.MostSignificantSlice - b.MostSignificantSlice; 
	if (diff >= 0){
		tmp = a;
		int size = b.buffer.size();
		for (int i = 0 ; i < size ; ++i){
			tmp.buffer[i] |= b.buffer[i];
		}
		for (int i = size; i < tmp.buffer.size() ; ++i){
			if (b.isPositive())
				tmp.buffer[i] |= 0x00;
			else
				tmp.buffer[i] |= MaxUint;
		}
		
	}else{
		tmp = b;
		int size = b.buffer.size();
		for (int i = 0 ; i < size ; ++i){
			tmp.buffer[i] |= a.buffer[i];
		}
		for (int i = size; i < tmp.buffer.size() ; ++i){
			if (a.isPositive())
				tmp.buffer[i] |= 0x00;
			else
				tmp.buffer[i] |= MaxUint;
		}
		
	}
	return tmp;
}
BigInteger operator ^(const BigInteger& a, const BigInteger& b)
{
		BigInteger tmp; 
	
	int diff =a.MostSignificantSlice - b.MostSignificantSlice; 
	if (diff >= 0){
		tmp = a;
		int size = b.buffer.size();
		for (int i = 0 ; i < size ; ++i){
			tmp.buffer[i] ^= b.buffer[i];
		}
		for (int i = size; i < tmp.buffer.size() ; ++i){
			if (b.isPositive())
				tmp.buffer[i] ^= 0x00;
			else
				tmp.buffer[i] ^= MaxUint;
		}
		
	}else{
		tmp = b;
		int size = b.buffer.size();
		for (int i = 0 ; i < size ; ++i){
			tmp.buffer[i] ^= a.buffer[i];
		}
		for (int i = size; i < tmp.buffer.size() ; ++i){
			if (a.isPositive())
				tmp.buffer[i] ^= 0x00;
			else
				tmp.buffer[i] ^= MaxUint;
		}
		
	}
	return tmp;
}
BigInteger operator <<(const BigInteger& a, const int i_shiftAmount)
{
	BigInteger tmp = a;
	tmp <<= i_shiftAmount;
	
	return tmp;
}
BigInteger operator >>(const BigInteger& a, const int i_shiftAmount)
{
	BigInteger tmp = a;
	tmp >>= i_shiftAmount;
	
	return tmp;
}
//------------ OTHER METHODS---------------

std::ostream& operator<<(std::ostream& out, const BigInteger& i_integer)
{
	return out << i_integer.asString();
}
//TODO : test
static BigInteger pow(const BigInteger& base, const BigInteger& exp) 
{
	BigInteger result = base;
	BigInteger ex = exp;

	while (ex > 0){
		result *= base;
		ex -=1;
	}

}
inline const bool BigInteger::isPositive() const
{	
	return ((this->buffer[this->buffer.size() - 1] & (0x01 << (sizeof(unsigned int) * 8  - 1))) == 0) ? true : false;

}

const bool BigInteger::IsEven() const
{

	unsigned val = this->buffer[0];
	unsigned aux = val & 0x01;
	return (this->buffer[0] & 0x01) == 0 ? true : false;
}

std::string BigInteger::asString() const
{
	std::string res;
	std::stringstream ss;
	BigInteger tmp;
	if (isPositive())
		tmp=*this;
	else{
		tmp= -*this;
	}
	while (tmp > 0){
		
		BigInteger mod = tmp % 10;
		tmp /= 10;
		ss << mod.buffer[0];
	}
	if (!isPositive())
		ss << "-";
	res = ss.str();
	
	std::reverse(res.begin(), res.end());
	return res;
}